Trung tâm thờ cúng của Heryshaf được đặt tại Herakleopolis Magna, một nome (quận) của Thượng Ai Cập. Theo phiến đá Palermo, việc thờ cúng Heryshaf diễn ra ngay từ thời kỳ Vương triều đầu tiên của Ai Cập, nhưng ngôi đền được biết đến sớm nhất dành riêng cho ông tại Herakleopolis có niên đại từ thời Trung Vương quốc. Heryshaf được tôn thờ cực thịnh vào Thời kỳ Chuyển tiếp thứ Nhất[1].

Nền móng của ngôi đền dưới thời Cổ Vương quốc sau đó không còn. Tuy nhiên, Flinder Petrie tìm thấy tàn tích của một ngôi đền tại Heracleopolis có niên đại từ thời Vương triều thứ 12[2]. Đền thờ Heryshef đã được mở rộng dưới triều Ramesses II, khi nhà vua đã thêm 16 cột đá granit khổng lồ được trang trí bằng hình lá cọ ở trên đầu[1], vốn được tái sử dụng từ những ngôi đền còn lại, có thể là của vua Djedkare Isesi hoặc Sahure. Yasuoka đoán rằng, con trai thứ tư của Ramesses II, hoàng tử Khaemweset, là người đã chỉ đạo công trình này[3].

Nimlot C, con trai của pharaon Osorkon II và thứ phi Djedmutesankh, là một trong những Đại tư tế của Heryshaf.